\section{Introduction}
\label{intro}
%Three points: 1) tenants accessable without exposing infrastructure.\\ 2) Manage distributed data collection\\ 3) data processing

Recent progress on network virtualization has made it possible to run
multiple virtual networks on a shared physical network, and decouple
the virtual network configuration from the underlying physical
network. Today, cloud tenants can specify sophisticated logical
network topologies among their virtual machines (VMs) and other network
appliances, such as routers or middleboxes, and flexibly define
policies on different virtual links~\cite{cloudnaas,stratos-tr}. The
underlying infrastructure then takes care of the realization of the
virtual networks by: for example, deploying VMs and virtual appliances,
instantiating the virtual links, setting up traffic shapers/bandwidth
reservations as needed, and logically isolating the traffic of
different tenants (e.g., using VLANs or tunnel IDs).  

%Once the network has been set up,
%tenants can configure the different virtual links in their network with
%the appropriate policies, such as traffic filters, broadcast domains,
%QoS etc.

While virtual networks can be implemented in a number of ways, we
focus on the common overlay-based approach adopted by several cloud
networking platforms. Examples that support such functionality include
OpenStack Neutron~\cite{openstack}, VMware/Nicira's NVP~\cite{nvp},
and IBM DOVE~\cite{dove}. Configuring the virtual networks requires
setting up tunnels between the deployed VM instances and usually
includes coordinated changes to the configuration of several VMs,
virtual switches, and potentially physical
switches and virtual/physical network appliances. Unfortunately, many
things could go wrong in such a complicated system. For example,
misconfiguration at the virtual network level might leave some VMs
disconnected, or receiving unintended flows, rogue VMs might overload
a virtual network with broadcast packets on a particular
virtual or physical switch.

%In the physical underlay network, an overloaded or
%misconfigured device may result in connectivity problems for multiple
%tenants, or middleboxes included in virtual network paths may
%erroneously transform or drop packets.

Because virtualization abstracts the underlying details, cloud tenants
lack the necessary visibility to perform troubleshooting. More
specifically, tenants only have access to their own virtual resources,
and, crucially, each virtual resource may map to multiple physical
resources, i.e., a virtual link may map to multiple 
physical links.  When a problem arises, there is no way today to
systematically obtain the relevant data from the appropriate 
locations and expose them to the tenant in a meaningful way to
facilitate diagnosis.

%% while I like it, I don't think we need this paragraph (aas)
%% This paper proposes a new framework for helping cloud tenants diagnose
%% such problems.  While similar problems arise in other ``physical''
%% networks, e.g., enterprise and ISP networks, we argue that
%% virtualization and extensive resource sharing in the cloud introduce
%% new challenges.  Yet, the increasingly software-defined nature of the
%% cloud provides unique opportunities for instrumenting the appropriate
%% diagnosis frameworks.

In this paper, we make the case for VND, a framework that enables a
cloud provider to offer sophisticated virtual network diagnosis as a
service to its tenants. Extracting the relevant data and exposing it
to the tenant forms the basis for VND. Yet, this is not trivial
because several requirements must be met when extracting and exposing the
data: we must preserve the abstracted view that the tenant is operating
on, ensure that data gathering and transfer do not impact performance
of ongoing connections, preserve isolation across tenants, and enable
suitable analysis to be run on the data, 
while scaling to large numbers of tenants in a cloud.

% Existing network diagnosis tools~\cite{ndb, ofrewind} require
% full access to the network infrastructure, which is not possible in
% the cloud. As a result, if anything goes wrong in tenants' virtual
% networks, the only thing they can do is to use tcpdump inside virtual
% machines and analyze the complicated packet traces by themselves,
% which is difficult even for network experts.

%Our design of VND leverages recent advances in software defined
%networking to help meet the requirements of maintaining the
%abstract view, ensuring low data gathering overhead and
%isolation. By carefully choosing how and where data collection and data
%aggregation happens, VND is designed to scale to many tenants.

%  This paper makes the case for a virtual network
% diagnosis framework that the cloud provider can offer as a service In
% this paper, we argue that virtual network diagnosis should be provided
% as a service to cloud tenants through an abstract interface. The cloud
% network platform should be able to perform flow monitoring for
% tenants, disambiguate the collected traffic for different tenants and
% delivery the traffic information for diagnosis without exposing the
% details about underlying network infrastructure.  We discuss the
% technical challenges of providing virtual network diagnosis service in
% terms of data collection overhead, system scalability to support many
% tenants and flow correlation. We layout the primary design of a
% Virtual Network Diagnosis framework, called VND.

VND exposes interfaces for configuring diagnosis and querying traffic
traces to cloud tenants for troubleshooting their virtual
networks. Tenants can specify a set of flows to monitor, and
investigate network problems by querying {\em their own} traffic
traces. VND controls the appropriate software switches to collect flow
traces and distributes traffic traces of different tenants into
``table servers''. VND co-locates flow capture points with table
servers to limit the data collection overhead. All the tenants'
diagnosis queries run on the distributed table servers.  To support
diagnosis requests from many tenants, VND moves data across the
network only when a query for that data is submitted.

Our design of VND leverages recent advances in software defined
networking to help meet the requirements of maintaining the abstract
view, ensuring low data gathering overhead and isolation. By carefully
choosing how and where data collection and data aggregation happens,
VND is designed to scale to many tenants.  VND is a significant
improvement over existing proposals for enterprise network diagnosis,
such as NDB~\cite{ndb}, OFRewind~\cite{ofrewind},
Anteater~\cite{anteater} and HSA~\cite{hsa}, which expose all the raw
network information. This leads to obvious scale issues, but it also
weakens isolation across tenants and exposes crucial information about
the infrastructure that may open the provider to attack.

%performs lazy query execution, which means a distributed query is
%executed only when a diagnosis request is submitted.

We show that several typical network diagnosis use cases can be easily
implemented using the query interface, including throughput, RTT and
packet loss monitoring.  We demonstrate how VND can help to detect and
scale the bottleneck middlebox in a virtual network.
%\aditya{examples include xxx: fill this} 
Our evaluation shows that the data collection can be
performed on hypervisor virtual switches without impacting 
existing user traffic, and the queries can be executed quickly on
distributed table servers. For example, throughput, RTT and packet loss
can be monitored in real time for a flow with several Gbps throughput.
%\aditya{elaborate on results} 
We believe our work demonstrates the feasibility of providing 
a virtual network diagnosis service in a cloud.

\revise{\#II}{
The contributions of this paper can be summarized as follows: 
%The contributions of VND can be summarized as follows:
\begin{itemize}
\item our work is the first to address the problem of virtual network diagnosis and the technical challenges 
of providing such a service in the cloud;
%a design of the VND framework for cloud tenants to diagnose their virtual network and application problems as well as the interface to the tenants.
\item we propose the design of a VND framework for cloud tenants to diagnose their virtual network and application 
problems and also propose the service interface to cloud tenants;
%optimizations to reduce overhead, achieve compatibility and improve scalability.
\item we propose optimization techniques to reduce overhead and achieve scalability for the VND 
framework;
%an implementation of VND, with experiments to show feasibility and measure overhead as well as simulations to show scalability.
\item we demonstrate the feasibility of VND through a real
  implementation, and conduct experiments measuring overhead along
  with simulations to show scalability.
\end{itemize}
}

The rest of this paper is organized as follows. Section~\ref{sec:back}
introduces the challenges and necessity of a virtual network diagnosis framework.
Section~\ref{sec:design} gives our VND design addressing the challenges.
Section~\ref{sec:impl} presents our VND implementation. We evaluate VND
feasibility in Section~\ref{sec:eval} and conclude this paper in Section~\ref{sec:conc}.

%Our work is not complete, and many research questions remain to be explored in the future. For example, 
%what is the scaling property of VND framework? How to correlated virtual network flows across multiple tunnels and 
%middleboxes that may transform the packet headers? However, we believe it shows the great potential of providing 
%virtual network diagnosis as a general service in cloud. 


%We argue that the virtual network diagnosis is difficult to the
%tenant due to three reasons. First, virtualization hides the
%visibility of the infrastructure to the tenants. The tenant only has
%access to his virtual appliances such as virtual machines and virtual
%middleboxes, which makes the information collection and problem
%locating difficult. Second, virtual networks have complex
%structures. The virtual network can be in arbitrary topologies and
%contains various network appliances such as middleboxes. This feature
%makes it obviously different from other overlay networks such as
%VPN. How to manage diagnosis in this distributed environment with
%security into consideration is not trivial. Third, tenants need
%sufficient ability to manipulate the collected information. Existing
%solutions seldom provide data manipulation that is flexible enough
%for data processing.

%In this paper, we propose our Virtual Network Diagnosis as a Service (VND) framework, in which we achieve the following contributions:

%1) VND provides virtual network diagnosis as a service to the tenant, in which the tenant can efficiently collect, parse and manipulate their network traffic via friendly interfaces. And VND still hides the infrastructure and other tenants' information for security issue.
%with access control from the cloud administrator.

%2) VND manages the virtual network diagnosis in a centralized way, which makes it easy to operate in the distributed environment. (The execution is still distributed to scale the system up.)
%, while the execution is in a distributed way to scale the system up.

%3) VND provides a query language on the collected data, which eases the tenant's data analysis.

%4) Our evaluation on the key components shows that VND does not
%impact existing system on both architecture and performance.  VND can
%also scale up with number of tenants by parallelism.  Tenants need
%tools to diagnosis networks in the case of problems.  In the cloud,
%existing tools has three limitations for the tenants. 1) Tenants
%cannot access the infrastructure. ( OFRewind, ndb ).  2) Hard to
%manage in distributed environment. (tcpdump). 3) Insufficient data
%processing. (wireshark).  We propose Virtual network diagnosis as a
%service (VND), which integrate data collection (tracing), data parse,
%and data process.
